


template <typename T>
void Random_Array (T data[], const int size, int range_a, int range_b, int fraction /*=0*/, bool sign_num /*=false*/)
//Заповнення масиву випадковими числами вказаного діапазону
//та заданою кількістю знаків у дробових числах
{
	long long mult = 1;
	T tmp_num;
	signed char znak;
	for (int i= 0; i< fraction; i++) mult*= 10;		//множник задає кількість знаків
		
	
	for (int i= 0; i< size; i++)
	{
		tmp_num = (rand() % (range_b - range_a) + range_a) + ((T)(rand()%mult)/mult)*(bool)fraction;
		znak= sign_num * rand()%2;					//Формула виключає використання умовного оператора 
		data[i] = tmp_num * (((znak-1)+znak)*(-1));	//
	}
}

template <typename T>
void Random_Table 	(	
						T ** data, 
						 size_t * index_col,
						 size_t row, 
						 size_t col, 
						 int range_a, 
						 int range_b, 
						const int fraction /*=0*/, 
						const bool sign_num /*=false*/
					)
//Заповнення динамічного масиву (N x M) випадковими числами вказаного діапазону
//та заданою кількістю знаків у дробових числах
{
	long long mult = 1;
	T tmp_num;
	signed char znak;
	for (int i= 0; i< fraction; i++) mult*= 10;		//множник задає кількість знаків
		
	
	for (size_t i= 0; i< row; ++i)
		for (size_t j= 0; j< col; ++j)
		{
			tmp_num = (rand() % (range_b - range_a) + range_a) + ((T)(rand()%mult)/mult)*(bool)fraction;
			znak= sign_num * rand()%2;					//Формула виключає використання умовного оператора 
			data[i][index_col[j]] = (T)(tmp_num * (((znak-1)+znak)*(-1)));	//
		}
}







template <typename T>
void Quick_Sort_par (T *data, const int left, const int right, bool type_sort /*=false*/)
//СОРТИРОВКА ХОАРА - найшвидший метод сортування O(n*log(2)n) = O(16)
//сотрування з параметром по зростанню (по замовчуванню) чи по спаданню (true)
//Можливо доцільніше використати 2 різні функції для збереження швидкості.
//ВАЖЛИВО: left та right - крайні елементи діапазону, які входять в цей діапазон 
{
	if (left >=right) return;
	const int ind = left + (right-left)/2;
	const T p = data[ind];
	int i = left;
	int j = right;

do {
	switch (type_sort)
	{
	case false:
	
		while (data[i] < p)
		{
			i++;
		}
		while (data[j] > p)
		{
			j--;
		}
	break;
	
	case true:
		while (data[i] > p)
		{
			i++;
		}
		while (data[j] < p)
		{
			j--;
		}
	break;
	}
	
	if (i <= j)
	{
		const T t= data[i];
		data[i] = data[j];
		data[j] = t;
		i++;
		j--;
	}
	
} while (i<=j);
	Quick_Sort_par(data, left, j, type_sort);
	Quick_Sort_par(data, i, right, type_sort);
}



template <typename T>
void Quick_Sort(T data[], const int left, const int right)
//СОРТИРОВКА ХОАРА - найшвидший метод сортування O(n*log(2)n) = O(16)
{
	if (left >=right) return;
	const int ind = left + (right-left)/2;
	const T p = data[ind];
	int i = left;
	int j = right;
	do {
		while (data[i] < p)
		{
			i++;
		}
		while (data[j] > p)
		{
			j--;
		}
		if (i <= j)
		{
			const T t= data[i];
			data[i] = data[j];
			data[j] = t;
			i++;
			j--;
		}
	} while (i<=j);
	Quick_Sort(data, left, j);
	Quick_Sort(data, i, right);
}


template <typename T>
void BobleSortDuo(T data[], const int size)
{
	for (int i= size-1; i>0; i--)
	{
		for (int j = 0; j<i; j++)
		{
			if (data[j]>data[j+1])
			{
				T temp = data[j+1];
				data[j+1] =  data[j];
				data[j] = temp;
			}
		}
	}
}

template <typename T>
void ShakeSort (T data[], const int size)
{
	int left = 0;
	int right = size - 1;
	while (left < right)
	{
		int k = left;
		for (int i = left; i<right; i++)
		{
			if (data[i] > data[i+1])
			{
				const T t = data[i];
				data[i] = data[i+1];
				data[i+1] = t;
				k = i;
			}
		}
		right = k;
		
		for (int i= right; i < left; i--)
		{
			if (data[i] < data[i-1])
			{
				const T t = data[i];
				data[i] = data[i-1];
				data[i-1] = t;
				k = i;
			}
			left = k;
		}
		
	}
}

template <typename T>
void Insert_Sort (T data[], const int size)
//СОРТУВАННЯ ВСТАВКОЮ 16/02/2014
{
	for (int i= 1; i< size; i++)
	{
		const T k= data[i];
		int j;
		for (j= i-1; (j>= 0) && (k<data[j]) ; j--)
		{
				data[j+1] = data[j];
		}
		data[j+1] = k;
	}
}

template <typename T>
void Insert_Sort_par (T data[], const int size, bool type_sort)
//СОРТУВАННЯ ВСТАВКОЮ 16/02/2014
//Сортування з вказанням напрямку сортування (вверх/вниз)
{
	for (int i= 1; i< size; i++)
	{
		const T k= data[i];
		int j;
		for (j= i-1; (j>= 0) && (type_sort ? k>data[j] : k<data[j]) ; j--)
		{
				data[j+1] = data[j];
		}
		data[j+1] = k;
	}
}



template <typename T>
void BolbSort(T data[], const int size)
{
	for (int i= size-1; i>0; i--)
	{
		for (int j = 0; j<i; j++)
		{
			if (data[j]>data[j+1])
			{
				T temp = data[j+1];
				data[j+1] =  data[j];
				data[j] = temp;
			}
		}
	}
}

template <typename T>
void SortData(T data[], const int size)
{
	for (int i = 0; i<size-1; i++)
	{
		T min_element = data[i];
		int index = i;
		for (int j=i+1; j<size; j++)
		{
			if (min_element > data[j])
			{
				min_element = data[j];
				index = j;
			}
			data[index] = data[i];
			data[i] = min_element;
		}

	}
}

template <typename TA>
void Manual_Infill_Array (TA data[], int size, int col)
{
	const int TAB= 8;
	
	system ("cls");
	for (int i= 0; i< size; i++)
	{
		cout << "\n\n\t" << "Set [" << (i+1) << "] cell of Array[" << size << "] : ";
		cin >> data[i];
		
		system ("cls");
		for (int j= 0; j<= i; j++)
		{
			if (!(j%5)) cout << "\n";
			cout << "\t" << data[j];
		}
		Line ((TAB+1)*col, '-');
	}
	//Line ((TAB+1)*col, '-');
}

template <typename T>
void Copy_Array (T *arr_src, T *arr_tar, const size_t size)
//Копіювання масиву
{
	for (size_t i= 0; i< size; i++)
	{
		*(arr_tar+i) = *(arr_src+i);
	}
}


template <typename T>
void Shuflle_Array (T *data, size_t size, size_t pass /*=1*/)
//Функція перемішування елементів масиву 
//pass - встановлення кількості проходів перемішування
{
	size_t sz = size*pass;
	int swap_i;
	int swap_j;
	for (size_t i= 0; i<sz; i++)
	{
		swap_i= rand() % size;
		swap_j= rand() % size;
		
		swap_a_b((data+swap_i), (data+swap_j));
	}

}

